package com.atwy.tree;

/**
 * 二叉排序树，BST
 * 对于二叉排序树的任何一个非叶子节点，要求左子节点的值比当前节点的值小，右子节点的值比当前节点的值大。
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] array = {7, 3, 10, 12, 5, 1, 4, 6, 9, 2};
        /** 创建BST */
        BinarySortTree bst = new BinarySortTree();
        for (int i = 0; i < array.length; i++) {
            bst.add(new Node(array[i]));
        }
        System.out.println("二叉查找树中序遍历：");
        // 中序遍历可以得到有序序列
        bst.middleOrder();
        /** 创建BST */

        /** 删除结点 */
        //bst.delNode(9);
        bst.delNode(7);
        // 删除之后再次遍历
        System.out.println("删除结点之后再次遍历：");
        bst.middleOrder();


        /** 查找结点 */

    }

}


class BinarySortTree {
    private Node root;

    /**
     * 添加结点
     *
     * @param node
     */
    public void add(Node node) {
        if (this.root == null) {
            this.root = node;
        } else {
            this.root.add(node);
        }
    }

    /**
     * 二叉树的删除
     * 1.删除叶子结点
     * 2.删除只有一棵子树的结点
     * 3.删除有两棵子树的结点
     * <p>
     *     做法：
     *      1.找到目标结点
     *      2.找到目标结点的父结点
     *      3.确定目标结点子结点情况，无、单左、单右、双子
     *      4.确定目标结点是父结点的左子结点还是右子结点
     *      5.主要分两种情况，目标结点有双子和没双子
     *      5.1.没有双子时，删除目标结点相当于给父结点的子结点赋值目标结点的子结点值
     *      5.2.有双子时，找到目标结点右子树的最小值，删除该最小结点，并把目标结点重新赋值为最小值。（左子树地最大值也行）
     * @param value
     */
    public void delNode(int value) {
        if (this.root == null) {
            return;
        }
        // 1.找到目标结点
        Node targetNode = search(value);
        // 没找到
        if (targetNode == null) {
            return;
        }
        // 如果当前二叉树只有一个结点
        if (this.root.left == null && this.root.right == null) {
            this.root = null;
            return;
        }

        // 1.目标结点只有一个子结点时
        Node parent = searchParent(value);

        if (targetNode.left != null && targetNode.right == null) {// 目标结点只有一个左子结点
            // 目标结点是其父结点的左子结点
            if (parent.left.value == targetNode.value) {
                parent.left = targetNode.left;
            } else if (parent.right.value == targetNode.value) {
                parent.right = targetNode.left;
            }
            return;
        }
        if (targetNode.left == null && targetNode.right != null) {// 目标结点只有一个右节点
            // 目标结点是其父结点的左子结点
            if (parent.left.value == targetNode.value) {
                parent.left = targetNode.right;
            } else if (parent.right.value == targetNode.value) {
                parent.right = targetNode.right;
            }
            return;
        }
        if (targetNode.left == null && targetNode.right == null) {// 目标结点没有子结点
            if (parent.left.value == targetNode.value) {
                parent.left = null;
            } else if (parent.right.value == targetNode.value) {
                parent.right = null;
            }
            return;
        }
        if (targetNode.left != null && targetNode.right != null) {// 目标结点有两个结点
            // 找到目标结点的右子树的最小结点，用临时变量保存
            Node minNode = getMinNode(targetNode.right);
            int temp = minNode.value;
            // 删除右子树的最小节点
            delNode(temp);
            // 目标结点重新赋值
            targetNode.value = temp;
        }

    }

    /**
     * 得到某结点下右子树最大的子结点
     *
     * @return
     */
    public Node getMaxNode(Node node) {
        if (node == null || node.right == null) {
            return node;
        }
        return node.lastRightNode();
    }

    /**
     * 得到某结点下左子树最小的子结点
     *
     * @return
     */
    public Node getMinNode(Node node) {
        if (node == null || node.right == null) {
            return node;
        }
        return node.lastLeftNode();
    }

    /**
     * 查找目标结点
     *
     * @param value
     * @return
     */
    public Node search(int value) {
        if (this.root == null) {
            return null;
        }
        return this.root.search(value);
    }

    /**
     * 查找目标结点的父结点
     *
     * @param value
     * @return
     */
    public Node searchParent(int value) {
        if (this.root == null) {
            return null;
        }
        return this.root.searchParent(value);
    }


    /**
     * 中序遍历
     */
    public void middleOrder() {
        if (this.root == null) {
            System.out.println("树为空，不能遍历~");
            return;
        }
        this.root.middleOrder();
    }

}

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    /**
     * 添加结点，比当前结点小的添加到左边，比当前结点大（等于）的添加到右边
     *
     * @param node
     */
    public void add(Node node) {
        if (node == null) {
            return;
        }
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    /**
     * 中序遍历，左-根-右
     */
    public void middleOrder() {
        // 左
        if (this.left != null) {
            this.left.middleOrder();
        }
        // 根
        System.out.println(this);

        // 右
        if (this.right != null) {
            this.right.middleOrder();
        }
    }

    /**
     * 根据值查找目标结点
     *
     * @param value
     * @return
     */
    public Node search(int value) {
        if (this.value == value) {
            return this;
        }
        // 比当前值小的查左子树
        if (value < this.value) {
            if (this.left == null) {
                return null;
            }
            return this.left.search(value);
        }
        // 比当前值大的查找右子树
        if (this.right == null) {
            return null;
        }
        return this.right.search(value);
    }

    /**
     * 根据值查找目标结点的父结点
     *
     * @param value
     * @return
     */
    public Node searchParent(int value) {
        // 当前结点满足条件，是目标结点的父结点，返回当前结点
        if ((this.left != null && this.left.value == value) ||
                this.right != null && this.right.value == value) {
            return this;
        }
        // 左子树
        if (value < this.value && this.left != null) {
            return this.left.searchParent(value);
        }
        // 右子树
        if (value >= this.value && this.right != null) {
            return this.right.searchParent(value);
        }

        return null;
    }

    /**
     * 得到该结点左子树最左边的叶子结点
     *
     * @return
     */
    public Node lastLeftNode() {
        if (this.left == null) {
            return this;
        }
        return this.left.lastLeftNode();
    }

    /**
     * 得到该结点右子树最右边的叶子结点
     *
     * @return
     */
    public Node lastRightNode() {
        if (this.right == null) {
            return this;
        }
        return this.right.lastRightNode();
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("Node{");
        sb.append("value=").append(value);
        sb.append('}');
        return sb.toString();
    }
}